import java.util.ArrayList;
import java.util.List;

// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class InorderTraversal {
    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> back = new ArrayList<>();
        dfs(back, root);
        return back;
    }

    public static void dfs(List<Integer> a, TreeNode root) {
        if (root == null) {
            return;
        }

        dfs(a, root.left);
        a.add(root.val);
        dfs(a, root.right);
    }

    public static void main(String[] args) {
        // 构建测试用的二叉树
        //       1
        //        \
        //         2
        //        /
        //       3
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        List<Integer> result = inorderTraversal(root);

        // 输出结果
        System.out.println("中序遍历结果: " + result);
        // 预期输出: [1, 3, 2]
    }
}